package leetcode.lcp0045;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	int[][] terrain;
	int[][] obstacle;
	int m, n;
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int[][] bicycleYard(int[] position, int[][] terrain, int[][] obstacle) {
		this.terrain = terrain;
		this.obstacle = obstacle;
		m = obstacle.length;
		n = obstacle[0].length;
		List<int[]> ret = new ArrayList<>();// 答案
		int arraySize = m * n;
		Set<Integer>[] indexs = new HashSet[arraySize];// 以某一个速度在这个位置开始。
		for (int i = 0; i < arraySize; i++) {
			indexs[i] = new HashSet<>();
		}
		int start = this.index(position[0], position[1], n);// 起始位置
		indexs[start].add(1);// 起始位置，速度1开始尝试过了
		boolean[] adds = new boolean[arraySize];// 添加过答案
		adds[start] = true;// 看例子，起始位置不算
		// 以1的速度从x,y位置开始，产生的可以达到速度1的位置，如果没加入过的ret就加入ret，indexs记录
		this.bicycleYard(1, position[0], position[1], ret, indexs, adds);
		// list转数组
		int[][] ans = new int[ret.size()][];
		int p = 0;
		for (int[] pos : ret) {
			ans[p++] = pos;
		}
		// 排序
		Arrays.sort(ans, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
		return ans;
	}

	private void bicycleYard(int speed, int x, int y, List<int[]> ret, Set<Integer>[] indexs, boolean[] adds) {
		// 骑行过程中速度不能为零或负值
//		System.out.println(speed + " " + x + " " + y);
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			int nextIndex = this.index(nextx, nexty, n);
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
				int nextSpeed = speed + terrain[x][y] - terrain[nextx][nexty] - obstacle[nextx][nexty];
				if (nextSpeed > 0) {
					if (nextSpeed == 1 && !adds[nextIndex]) {
						adds[nextIndex] = true;
						ret.add(new int[] { nextx, nexty });
					}
					Set<Integer> set = indexs[nextIndex];
					if (!set.contains(nextSpeed)) {
						set.add(nextSpeed);
						this.bicycleYard(nextSpeed, nextx, nexty, ret, indexs, adds);
					}
				}
			}
		}
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

	@Override
	public void debug4() {
		H.compare(H.str2array1("[[0,1],[1,0],[1,1]]"),
				this.bicycleYard(H.str2array3("[0,0]"), H.str2array1("[[0,0],[0,0]]"), H.str2array1("[[0,0],[0,0]]")));
		H.compare(H.str2array1("[[0,1]]"),
				this.bicycleYard(H.str2array3("[1,1]"), H.str2array1("[[5,0],[0,6]]"), H.str2array1("[[0,6],[7,0]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		List<Integer> list = new ArrayList<>();
		list.add(1);
		for (int num : list) {
			System.out.println(num);

		}
	}

}
